#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
#include<set>
using namespace std;


class MaxQueue {
public:
    MaxQueue() {
        
    }
    
    int max_value() {
        if(Q.empty()){
            return -1;
        }
        return T.front();
    }
    
    void push_back(int value) {
        while(!T.empty()&&T.back()<value){
            T.pop_back();
        }
        T.push_back(value);
        Q.push(value);
    }
    
    int pop_front() {
        if(Q.empty()){
            return -1;
        }
        int temp = Q.front();
        if(T.front()==temp){
            T.pop_front();
        }
        Q.pop();
        return temp;

    }
public:
   
    queue<int> Q;
    deque<int> T;
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */


int main(){
    MaxQueue Q;
    Q.push_back(1);
    Q.push_back(2);
    cout<<Q.max_value()<<endl;
    cout<<Q.pop_front()<<endl;
    cout<<Q.max_value()<<endl; 
}